/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package HojaTrabajo3;

/**
 * Quicksort.java
 * @author Douglas Dávila
 * Ordenamiento por algoritmo rapido
 */
public class QuickSort  {
    /**arreglo de numeros a ordenar*/
	private Comparable[] numbers;
	/**pivote del algoritmo de ordenamiento rapido*/
	private int number;
        /**
         * tomado en: http://www.vogella.com/articles/JavaAlgorithmsQuicksort/article.html
         * @param values el arreglo a ordenar
         */
	public void quickSort(Comparable[] values) {
		// Check for empty or null array
		if (values ==null || values.length==0){
			return;
		}
		this.numbers = values;
		number = values.length;
		sort(0, number - 1);
	}
        /**
         * tomado en: http://www.vogella.com/articles/JavaAlgorithmsQuicksort/article.html
         * @param low
         * @param high 
         */
	private void sort(int low, int high) {
		int i = low, j = high;
		// Get the pivot element from the middle of the list
		int pivot = (Integer)numbers[low + (high-low)/2];

		// Divide into two lists
		while (i <= j) {
			// If the current value from the left list is smaller then the pivot
			// element then get the next element from the left list
			while ((Integer)numbers[i] < pivot) {
				i++;
			}
			// If the current value from the right list is larger then the pivot
			// element then get the next element from the right list
			while ((Integer)numbers[j] > pivot) {
				j--;
			}

			// If we have found a values in the left list which is larger then
			// the pivot element and if we have found a value in the right list
			// which is smaller then the pivot element then we exchange the
			// values.
			// As we are done we can increase i and j
			if (i <= j) {
				exchange(i, j);
				i++;
				j--;
			}
		}
		// Recursion
		if (low < j)
			sort(low, j);
		if (i < high)
			sort(i, high);        
        }
        /**
         * tomado en: http://www.vogella.com/articles/JavaAlgorithmsQuicksort/article.html
         * @param i
         * @param j 
         */
	private void exchange(int i, int j) {
		int temp = (Integer)numbers[i];
		numbers[i] = numbers[j];
		numbers[j] = temp;
	} 
} 

